238D - Tape Programming - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=1.1e5;
char s[N];
int n,m=1,q,fir[N],sec[N],f[N*50][10];
void add(int x,int v)
{
if(!fir[x]) fir[x]=m;
else if(!sec[x] && fir[x+1]) sec[x]=m;
for(int i=0;i<=9;i++)
f[m][i]=f[m-1][i]+(i==v);
}
int main()
{
cin>>n>>q; scanf("%s",s+1);

fir[0]=1;
for(int p=1,d,i,op;p<=n;p++) if(!fir[p])
{
for(d=1,i=p,op=0;p<=i && i<=n;i+=d,m++)
{
if(isdigit(s[i]))
add(i,s[i]---'0'),op=0;
else
{
add(i,-1);
if(s[i]<'0') continue;
d=s[i]^'<'?1:-1;
if(op) s[op]=0;
op=i;
}
}
add(i,-1); m++;
}
fir[n+1]=m;

for(int l,r,ll,rr;q--;)
{
cin>>l>>r;
ll=fir[l]-1,rr=min(sec[l-1]?sec[l-1]:m,fir[r+1])-1;
for(int i=0;i<=9;i++)
printf("%d%c",f[rr][i]-f[ll][i]," \n"[i==9]);
}
return 0;
}